vertex cover について

Words near each other

Dictionary Lists

mini英和辞書

翻訳と辞書　辞書検索 [ 開発暫定版 ]

スポンサードリンク

vertex cover ：ウィキペディア英語版

vertex cover
In the mathematical discipline of graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set.
The problem of finding a minimum vertex cover is a classical optimization problem in computer science and is a typical example of an NP-hard optimization problem that has an approximation algorithm. Its decision version, the vertex cover problem, was one of Karp's 21 NP-complete problems and is therefore a classical NP-complete problem in computational complexity theory. Furthermore, the vertex cover problem is fixed-parameter tractable and a central problem in parameterized complexity theory.
The minimum vertex cover problem can be formulated as a half-integral linear program whose dual linear program is the maximum matching problem.
== Definition ==

Formally, a vertex cover

V'

of an undirected graph

G=(V, E)

is a subset of

V

such that

\forall uv \in E : u \in V' \lor v \in V'

, that is to say it is a set of vertices

V'

where every edge has at least one endpoint in the vertex cover

V'

. Such a set is said to ''cover'' the edges of

G

. The following figure shows two examples of vertex covers, with some vertex cover

V'

marked in red.
:File:Vertex-cover.svg
A ''minimum vertex cover'' is a vertex cover of smallest possible size. The vertex cover number

\tau

is the size of a minimum vertex cover, i.e.

\tau = |V'|

. The following figure shows examples of minimum vertex covers in the previous graphs.
:File:Minimum-vertex-cover.svg

抄文引用元・出典: フリー百科事典『ウィキペディア（Wikipedia）』
■ウィキペディアで「vertex cover」の詳細全文を読む

スポンサードリンク

翻訳と辞書 : 翻訳のためのインターネットリソース